#include "global.h"

/* Minimum surface of a room */
static int Smin;

/* Dimensions of the dungeon */
static int dim_x_init;
static int dim_y_init;

/* Worst y/x and x/y ratios accepted. */
#define WORST_ROOM_RATIO 2.0

/** Check if the two proposed room sizes satisfy the minimal surface criteria or not.
 */
int check_surf(int w_creator, int h_creator, int w_newroom, int h_newroom) 
{
	if ((w_creator * h_creator  > Smin) && (h_newroom * w_newroom  > Smin))
		return 1;
	
	return 0;
}

/**
 * Try to cut a room of dimensions dim_x and dim_y, horizontally or vertically
 * depending on the value of vert, with a ratio r.
 *
 * This function picks a ratio for the cut and sets r accordingly.
 */
static int trycut(int dim_x, int dim_y, int *r, int vert)
{
	/*
	 * Example computation for a vertical cut : 
	 *
	 * x1 + x2 = dim_x
	 * x1 = r * x
	 * x2 = (1-r) * x
	 * log(x1/y) <= b, b constant
	 * log(x1/y) >= -b
	 *
	 * =>  y/(a * x) <= r <= a * y/x 
	 * and 1-(ya)/x <= r <= 1 - y/(ax) 
	 *
	 * with a = exp(b)
	 */
	float rmin = 1, rmin2 = 1, rmax = 0, rmax2 = 0;

	switch (vert) {
		case 0: // coupe horizontale
			rmax = WORST_ROOM_RATIO * (float)dim_x / dim_y;
			rmin2 = (1.0/WORST_ROOM_RATIO) * dim_x / dim_y;
			break;
		case 1: // coupe verticale
			rmax = WORST_ROOM_RATIO * (float)dim_y / dim_x;
			rmin2 = (1.0/WORST_ROOM_RATIO) * dim_y / dim_x;
			break;
	}


	rmin = 1 - rmax;
	rmax2 = 1 - rmin2;

	rmax = rmax > rmax2 ? rmax2 : rmax;
	rmin = rmin < rmin2 ? rmin2 : rmin;

	if (rmax < rmin) {
		// No cut possible this way
		return 0;
	}

	// Pick a cut ratio
	*r = 100.0 * (rmin + (rmax - rmin) * ((float)rand() / (float)RAND_MAX));

	return 1;
}

/**
 * Make a decision about a cut in a room: whether to cut at all,
 *  what way to cut, and at what position
 */
static int cut(int dim_x, int dim_y, int *r)
{
	int ret = 2; //do not cut
	// linear probability of cut
	float chancetocut =  (1 / ( dim_x_init * dim_y_init)) * dim_x * dim_y - (Smin / ( dim_x_init * dim_y_init - Smin));
	float p=rand()%10000+1;

	// Test whether to cut at all
	if (p/10000< chancetocut){
		// no cut
		return 2;
	}

	// Pick a random direction to cut along
	ret = rand()%2;

	// Try to cut along this direction
	if (!trycut(dim_x, dim_y, r, ret)) {
		// If we cannot, try the other direction
		if(!trycut(dim_x, dim_y, r, !ret))
			return 2;
		else ret = !ret;
	}

	// Rooms need to be 4 tiles wide at least
	switch (ret) {
		case 0: //horizontal cut
			if ((*r/100.0 * dim_y) < 4 || ((100.0-*r)/100.0 * dim_y) < 4)
				return 2;
			break;
		case 1:
			if ((*r/100.0 * dim_x) < 4 || ((100.0-*r)/100.0 * dim_x) < 4)
				return 2;
			break;
	}

	return ret;
}

static void deriv_P(int id) 
{
	int p;
	int prop;
	int x=rooms[id].x;
	int y=rooms[id].y;
	int creator= id;
	int dim_x=rooms[creator].w;
	int dim_y=rooms[creator].h;
	int newroom = total_rooms;
	p = cut(dim_x, dim_y, &prop);

	int w_creator = dim_x;
	int h_creator = dim_y;
	int w_newroom = dim_x;
	int h_newroom = dim_y;
	int x_newroom = x;
	int y_newroom = y;

	/*
	  Two rules : 
	  P -> P h P | P -> P v P

	  h horizontal cut
	  v vertical cut
	 */
	switch (p) {
		case 0:
			/* Horizontal cut */
			h_creator = rooms[creator].h*prop/100.0;
			h_newroom = dim_y - h_creator;
			y_newroom = y + h_creator;
			break;
		case 1:
			/* Vertical cut */
			w_creator = rooms[creator].w*prop/100.0;
			w_newroom = dim_x - w_creator;
			x_newroom = x + w_creator;
			break;
		default :	
			return;
	}

	if (!check_surf(w_creator,h_creator,w_newroom,h_newroom)){
		return;
	}
	rooms[newroom].x = x_newroom;
	rooms[newroom].y = y_newroom;
	rooms[newroom].w = w_newroom;
	rooms[newroom].h = h_newroom;
	rooms[creator].w = w_creator;
	rooms[creator].h = h_creator;
	igraph_add_vertices(&dungeon_graph, 1, NULL);
	set_roominfo(&dungeon_graph, newroom, &rooms[newroom]);
	total_rooms++;
	mapgen_draw_room(rooms[newroom].x, rooms[newroom].y, rooms[newroom].w, rooms[newroom].h, newroom);
	mapgen_draw_room(rooms[creator].x, rooms[creator].y, rooms[creator].w, rooms[creator].h, creator);
	deriv_P(id);
	deriv_P(newroom);
}

static int change_cote(int depart, int ajout){

	if (depart> 7){
		return ajout;
	}
	switch (depart) {
	      case 4 : {
			switch (ajout) {
			      case 6 : {return 0;}break;
			      case 7 : {return 1;}break;
   			      default : {return ajout;} break;
			}
		}break;
	      case 5 : {
			switch (ajout) {
			      case 6 : {return 2;}break;
			      case 7 : {return 3;}break;
   			      default : {return ajout;} break;
			}
		}break;
	      case 6 : {
			switch (ajout) {
			      case 4 : {return 0;}break;
			      case 5 : {return 2;}break;
   			      default : {return ajout;} break;
			}
		}break;
	      case 7 : {
			switch (ajout) {
			      case 4 : {return 1;}break;
			      case 5 : {return 3;}break;
   			      default : {return ajout;} break;
			}
		}break;
	      default : {return ajout;}break;
	}
}

/**
 * Is the given position a room corner?
 */
static int is_room_corner(int x,int y)
{
	int id = mapgen_get_room(x,y);
	if ((x == rooms[id].x && y == rooms[id].y) || 
			(x == rooms[id].x && y == rooms[id].y + rooms[id].h - 1) || 
			(x == rooms[id].x + rooms[id].w - 1 && y == rooms[id].y) || 
			(x == rooms[id].x + rooms[id].w - 1 && y == rooms[id].y + rooms[id].h - 1)){
		return 1;
	}
	return 0;
}

static void adj(struct cplist_t cplist, int x,int y, int* nx, int* ny) {
	switch (cplist.t) {
	      case UP:
			*nx = x;
			*ny = y - 1;
			break;
	      case DOWN:
			*nx = x;
			*ny = y + 1;
			break;
	      case LEFT:
			*nx = x - 1;
			*ny = y;
			break;
	      case RIGHT:
			*nx = x + 1;
			*ny = y;
			break;
	      default:
			*nx = 0;
			*ny = 0;
			break;
	}
}

/**
 * Join two rooms by breaking the wall between them
 */
void fusion(int id, int cible)
{
	struct cplist_t cplist[100];
	int correct_directory[100];

	memset(correct_directory, -1, 100*sizeof(int));
	memset(cplist, -1, 100*sizeof(int));
	
	int nb_max;
	nb_max=find_connection_points(id, cplist);
	int k=0;
	int l=0;//index du tableau correct_directory
	int nx, ny;
	int x,y;
	while (k<nb_max){
		x = cplist[k].x;
		y = cplist[k].y;
		nx=0;
		ny=0;
		adj(cplist[k],x,y,&nx,&ny);
		if (cplist[k].r==cible && !is_room_corner(x,y) && !is_room_corner(nx,ny)) {
			correct_directory[l]=k;
			l++;
		}
		k++;
	}
	if (l==0){
		printf("erreur dans fusion\n");
		printf("fusion de %d=(%d,%d) avec %d=(%d,%d)\n",id,rooms[id].x,rooms[id].y,cible,rooms[cible].x,rooms[cible].y);
		printf("dim de %d=(%d,%d) avec %d=(%d,%d)\n",id,rooms[id].w,rooms[id].h,cible,rooms[cible].w,rooms[cible].h);
		return;
	}
	
	for (k=0;k<l;k++){
		x=cplist[correct_directory[k]].x;
		y=cplist[correct_directory[k]].y;
		nx=0;
		ny=0;
		adj(cplist[correct_directory[k]],x,y,&nx,&ny);
		mapgen_put_tile(x, y, 12, id);
		mapgen_put_tile(nx, ny, 12, cible);
		
		if(k==0  && cplist[correct_directory[k]].t==UP){
			if (rooms[id].x>rooms[cible].x){
				mapgen_put_tile(x-1, y, change_cote(mapgen_get_tile(x-1,y),7), id);
				mapgen_put_tile(nx-1, ny,change_cote(mapgen_get_tile(nx-1,ny),1), cible);
			} else if (rooms[id].x==rooms[cible].x){
				mapgen_put_tile(x-1, y,change_cote(mapgen_get_tile(x-1,y),7) , id);
				mapgen_put_tile(nx-1, ny,change_cote(mapgen_get_tile(nx-1,ny),7) , cible);
			} else {
				mapgen_put_tile(x-1, y,change_cote(mapgen_get_tile(x-1,y),3) , id);
				mapgen_put_tile(nx-1, ny,change_cote(mapgen_get_tile(nx-1,ny),7) , cible);
			}
		}
		
		if( k==l-1 && cplist[correct_directory[k]].t==UP){
			if (rooms[id].x+rooms[id].w>rooms[cible].x+rooms[cible].w){
				mapgen_put_tile(x+1, y, change_cote(mapgen_get_tile(x+1,y),2), id);
				mapgen_put_tile(nx+1, ny, change_cote(mapgen_get_tile(nx+1,ny),6), cible);
			} else if (rooms[id].x+rooms[id].w==rooms[cible].x+rooms[cible].w){
				mapgen_put_tile(x+1, y, change_cote(mapgen_get_tile(x+1,y),6), id);
				mapgen_put_tile(nx+1, ny, change_cote(mapgen_get_tile(nx+1,ny),6), cible);
				
			} else {
				mapgen_put_tile(x+1, y, change_cote(mapgen_get_tile(x+1,y),6), id);
				mapgen_put_tile(nx+1, ny, change_cote(mapgen_get_tile(nx+1,ny),0), cible);
			}
		}
		
		if(k==0  && cplist[correct_directory[k]].t==DOWN){
			if (rooms[id].x<rooms[cible].x){
				mapgen_put_tile(x-1, y, change_cote(mapgen_get_tile(x-1,y),1), id);
				mapgen_put_tile(nx-1, ny,change_cote(mapgen_get_tile(nx-1,ny),7), cible);
			}else if (rooms[id].x==rooms[cible].x){
				mapgen_put_tile(x-1, y,change_cote(mapgen_get_tile(x-1,y),7) , id);
				mapgen_put_tile(nx-1, ny,change_cote(mapgen_get_tile(nx-1,ny),7) , cible);
			} else {
				mapgen_put_tile(x-1, y,change_cote(mapgen_get_tile(x-1,y),7) , id);
				mapgen_put_tile(nx-1, ny,change_cote(mapgen_get_tile(nx-1,ny),3) , cible);
			}
		}
		
		if( k==l-1 && cplist[correct_directory[k]].t==DOWN){
			if (rooms[id].x+rooms[id].w<rooms[cible].x+rooms[cible].w){
				mapgen_put_tile(x+1, y, change_cote(mapgen_get_tile(x+1,y),6), id);
				mapgen_put_tile(nx+1, ny, change_cote(mapgen_get_tile(nx+1,ny),2), cible);
			}else if (rooms[id].x+rooms[id].w==rooms[cible].x+rooms[cible].w){
				mapgen_put_tile(x+1, y, change_cote(mapgen_get_tile(x+1,y),6), id);
				mapgen_put_tile(nx+1, ny, change_cote(mapgen_get_tile(nx+1,ny),6), cible);
			} else {
				mapgen_put_tile(x+1, y, change_cote(mapgen_get_tile(x+1,y),0), id);
				mapgen_put_tile(nx+1, ny, change_cote(mapgen_get_tile(nx+1,ny),6), cible);
			}
		}
		
		if(k==0  && cplist[correct_directory[k]].t==LEFT){
			if (rooms[id].y>rooms[cible].y){
				mapgen_put_tile(x, y-1, change_cote(mapgen_get_tile(x,y-1),5), id);
				mapgen_put_tile(nx, ny-1, change_cote(mapgen_get_tile(nx,ny-1),2), cible);
			}else if (rooms[id].y==rooms[cible].y){
				mapgen_put_tile(x, y-1, change_cote(mapgen_get_tile(x,y-1),5), id);
				mapgen_put_tile(nx, ny-1, change_cote(mapgen_get_tile(nx,ny-1),5), cible);
			} else {
				mapgen_put_tile(x, y-1, change_cote(mapgen_get_tile(x,y-1),3), id);
				mapgen_put_tile(nx, ny-1, change_cote(mapgen_get_tile(nx,ny-1),5), cible);
			}
		}
		
		if(k==l-1  && cplist[correct_directory[k]].t==LEFT){
			if (rooms[id].y+rooms[id].h<rooms[cible].y+rooms[cible].h){
				mapgen_put_tile(x, y+1, change_cote(mapgen_get_tile(x,y+1),4), id);
				mapgen_put_tile(nx, ny+1, change_cote(mapgen_get_tile(nx,ny+1),0), cible);
			}else if (rooms[id].y+rooms[id].h==rooms[cible].y+rooms[cible].h){
				mapgen_put_tile(x, y+1, change_cote(mapgen_get_tile(x,y+1),4), id);
				mapgen_put_tile(nx, ny+1, change_cote(mapgen_get_tile(nx,ny+1),4), cible);
			} else {
				mapgen_put_tile(x, y+1, change_cote(mapgen_get_tile(x,y+1),1), id);
				mapgen_put_tile(nx, ny+1, change_cote(mapgen_get_tile(nx,ny+1),4), cible);
			}
		}
		
		if(k==0  && cplist[correct_directory[k]].t==RIGHT){
			if (rooms[id].y<rooms[cible].y){
				mapgen_put_tile(x, y-1, change_cote(mapgen_get_tile(x,y-1),2), id);
				mapgen_put_tile(nx, ny-1, change_cote(mapgen_get_tile(nx,ny-1),5), cible);
			}else if (rooms[id].y==rooms[cible].y){
				mapgen_put_tile(x, y-1, change_cote(mapgen_get_tile(x,y-1),5), id);
				mapgen_put_tile(nx, ny-1, change_cote(mapgen_get_tile(nx,ny-1),5), cible);
			} else {
				mapgen_put_tile(x, y-1, change_cote(mapgen_get_tile(x,y-1),5), id);
				mapgen_put_tile(nx, ny-1, change_cote(mapgen_get_tile(nx,ny-1),3), cible);
			}
		}
		
		if(k==l-1  && cplist[correct_directory[k]].t==RIGHT){
			if (rooms[id].y+rooms[id].h>rooms[cible].y+rooms[cible].h){
				mapgen_put_tile(x, y+1, change_cote(mapgen_get_tile(x,y+1),0), id);
				mapgen_put_tile(nx, ny+1, change_cote(mapgen_get_tile(nx,ny+1),4), cible);
			}else if ((rooms[id].y+rooms[id].h)==(rooms[cible].y+rooms[cible].h)){
				mapgen_put_tile(x, y+1, change_cote(mapgen_get_tile(x,y+1),4), id);
				mapgen_put_tile(nx, ny+1, change_cote(mapgen_get_tile(nx,ny+1),4), cible);
			} else {
				mapgen_put_tile(x, y+1, change_cote(mapgen_get_tile(x,y+1),4), id);
				mapgen_put_tile(nx, ny+1, change_cote(mapgen_get_tile(nx,ny+1),1), cible);
			}
		}
	}
}

static void add_rel(int x, int y , enum connection_type type, int cible){
	int id =mapgen_get_room(x,y);
	if ((((rooms[id].x!=rooms[cible].x) || (rooms[id].w != rooms[cible].w)) &&(type==UP || type==DOWN))|| (((rooms[id].y != rooms[cible].y) || (rooms[id].h != rooms[cible].h)) &&(type==RIGHT || type==LEFT))){
		struct cplist_t *cplist ;
		cplist=malloc(sizeof(struct cplist_t)*100);
		memset(cplist,-1,100*sizeof(int));
		int nb_max;
		nb_max=find_connection_points(id, cplist);
		int k=0;
		// tableau de tout les cases a fusionner dans la bonne direction
		// pas plus de 100 possibilités par coté
		int * correct_directory=malloc(sizeof(int)*100);
		memset(correct_directory,-1,100*sizeof(int));
		int l=0;//index du tableau correct_directory
		while (k<nb_max){
			int x2,y2;
			x2 = cplist[k].x;
			y2 = cplist[k].y;
			int nx,ny;
			nx=0;
			ny=0;
			adj(cplist[k],x2,y2,&nx,&ny);
			if (cplist[k].r==cible && !is_room_corner(x2,y2) && !is_room_corner(nx,ny)){
				correct_directory[l]=k;
				l++;
			}
			k++;
		}
                free(correct_directory);
		free(cplist);
                int p=rand()%4;
		if (p==0 && l){
			fusion(id,cible);
		}else{
			MakeConnect(x,y,type);
		}
		igraph_add_edge(&dungeon_graph,id,cible);
		add_edge_weight(id,cible);
	} else {
		MakeConnect(x,y,type);
		igraph_add_edge(&dungeon_graph,id,cible);
		add_edge_weight(id,cible);
	}
}

void bulldozer(unsigned char *seen, int r)
{
	struct cplist_t cplist[300];
	seen[r] = 1;
	int max_connections;
	max_connections = find_connection_points(r, cplist);
	int exist; // vrai si la connexion existe déjà

	// Pick a random connection to do
	int i = rand() % max_connections;
	int x2=cplist[i].x;
	int y2=cplist[i].y;
	switch (cplist[i].t){
		case RIGHT : x2++; break;
		case DOWN : y2++; break;
		default:
					break;
	}
	
	// si déjà connecté on ne crée pas de nouvelle connexion et le bulldozer s'arrete
	igraph_are_connected(&dungeon_graph, r,cplist[i].r,&exist);
	if (exist){
		return;
	}
	// sinon ajout
	add_rel(cplist[i].x,cplist[i].y,cplist[i].t,cplist[i].r);
	// on lance le bulldozer dans la salle voisine
	//getchar();
	bulldozer(seen, mapgen_get_room(x2,y2));
}

static void launch_buldo()
{
	int r;
	igraph_bool_t connected;
	unsigned char seen[total_rooms];
	memset(seen, 0, total_rooms);

	// Start bulldozers so that every room has been seen
	for (r=0; r < total_rooms; r++) {
		if (!(seen[r])) {
			bulldozer(seen, r);
		}
	}
	
	igraph_is_connected(&dungeon_graph, &connected, IGRAPH_STRONG);

	// Check whether the graph is connected.
	// If it is not, ensure connectivity by connecting each vertex from 
	// a component that is not 0's to 0's whenever possible, until we have
	// connectivity.
	while (!connected) {
		igraph_vector_t mbr;
		igraph_vector_init(&mbr, 1);
		igraph_integer_t nbc;
		igraph_clusters(&dungeon_graph, &mbr, NULL, &nbc, IGRAPH_STRONG);
		
		int a = 0;
		int recalculate_components = 0;
		do {
#ifdef DEBUG			
			printf("Vertex %d belongs to connected component %f\n", a, VECTOR(mbr)[a]);
#endif
			struct cplist_t neigh[100];
			int n, nbconn, prevneigh = -1;
			nbconn = find_connection_points(a, neigh);
			for (n = 0; n < nbconn; n++) {
				if (neigh[n].r == prevneigh)
					continue;

				prevneigh = neigh[n].r;

				if (VECTOR(mbr)[neigh[n].r] != VECTOR(mbr)[a]) {
					// Found a possible connection to another connected component: make it and recalculate
					int connected;
					igraph_are_connected(&dungeon_graph, a, neigh[n].r, &connected);

					if (!connected) {
#ifdef DEBUG
						printf("Vertex %d can be connected to vertex %d\n", a, neigh[n].r);
#endif
						add_rel(neigh[n].x, neigh[n].y, neigh[n].t, neigh[n].r); 

						if (!(rand()%5))
							// Allow for more than one connection between two connected components.
							recalculate_components = 1;

						break;
					}
				}
			}
		} while (!recalculate_components && (a++ < igraph_vcount(&dungeon_graph)));
		igraph_vector_destroy(&mbr);
		igraph_is_connected(&dungeon_graph, &connected, IGRAPH_STRONG);
	}
}

static int launch(int dim_x, int dim_y, int dim_Smin) 
{
	dim_x_init=dim_x;
	dim_y_init=dim_y;
	Smin=dim_Smin;
	total_rooms=0;
	
	if (dim_x*dim_y<Smin){
		printf("Asked for a room minimal surface larger than the dungeon size.\n");
		return -1;
	}

	// Create first room
	mapgen_draw_room(0, 0, dim_x_init, dim_y_init, total_rooms);

	rooms[total_rooms].x = 0;
	rooms[total_rooms].y = 0;
	rooms[total_rooms].w = dim_x_init;
	rooms[total_rooms].h = dim_y_init;
	igraph_add_vertices(&dungeon_graph, 1, NULL);
	set_roominfo(&dungeon_graph, total_rooms, &rooms[total_rooms]);
	total_rooms++;

	// Recursively cut
	deriv_P(0);

	// Make connections between rooms
	launch_buldo();
	return 0;
}

int generate_dungeon_gram(int w, int h){
	return launch(w,h,40);
}
